int maxDepth(struct TreeNode* root) {
	if (root == NULL)
		return 0;
	int left = maxDepth(root->left);
	int right = maxDepth(root->right);
	return left > right ? left + 1 : right + 1;
}
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if (p == NULL && q == NULL)
        return true;
    if (p == NULL || q == NULL)
        return false;
    if (p->val != q->val)
        return false;
    return  isSameTree(p->left, q->left) && isSameTree(p->right, q->right);

}
bool isUnivalTree(struct TreeNode* root) {
    if (root == NULL)
        return true;
    if (root->left && root->left->val != root->val)
        return false;
    if (root->right && root->right->val != root->val)
        return  false;
    return isUnivalTree(root->left) && isUnivalTree(root->right);


}
struct TreeNode* invertTree(struct TreeNode* root) {
    if (root == NULL)
        return NULL;
    struct TreeNode* left = invertTree(root->left);
    struct TreeNode* right = invertTree(root->right);
    root->left = right;
    root->right = left;
    return root;

}
int BinaryTreeSize(struct TreeNode* root)
{

    return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;





}
void  aapreorderTraversal(struct TreeNode* root, int* a, int* pi)
{
    if (root == NULL)
        return;
    a[(*pi)++] = root->val;
    aapreorderTraversal(root->left, a, pi);
    aapreorderTraversal(root->right, a, pi);




}


int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    *returnSize = BinaryTreeSize(root);
    int* a = (int*)malloc(*returnSize * sizeof(int));
    int i = 0;
    aapreorderTraversal(root, a, &i);

    return a;




}